package offer;

public class offer12 {
}
class Solution12 {
    public static boolean exist(char[][] board, String word) {
//        思路：从字符串的第一个字符出发在board中寻找，如果找到了，就找下一个字符
//        下一个字符，如果上下左右都不是下一个字符，重新寻找第一个字符
//        如果是下一个字符，则下下个字符不能在已经选过的地方找
        char [] s = word.toCharArray();
        int len = s.length-1;
        boolean [][] bd = new boolean[board.length][board[0].length];
        boolean flag = false;
        for (int i  = 0; i <board.length ; i++) {
            for (int j = 0; j <board[0].length ; j++) {
                if(board[i][j] ==s[0])
                {      bd[i][j]=true;
                      flag= find(s,len-1,i,j,board.length,board[0].length,board,bd);
                      bd[i][j] = false;
                }
                if(flag==true)
                 break;
            }
            if(flag==true)break;
        }
        return flag;
    }
   static int temp =1;

    private static boolean  find(char[] s, int len,int i,int j,int m,int n,char[][] board,boolean [][] bd ) {
        if(len==-1)return true;
        if(i-1>=0&&bd[i-1][j]==false&&s[temp]==board[i-1][j])
        {

                temp = temp+1;
                bd[i-1][j] = true;
                if(find(s,len-1,i-1,j,m,n,board,bd)) return true;
                else {
                    temp--;
                    bd[i - 1][j] = false;
                }

        }
        if(i+1<m&&bd[i+1][j]==false&&s[temp]==board[i+1][j])
        {
            System.out.println(s[temp]);
            System.out.println(board[i+1][j]);

                temp = temp+1;
                bd[i+1][j] = true;
               if(find(s,len-1,i+1,j,m,n,board,bd)) return true;
               else {
                   temp--;
                   bd[i + 1][j] = false;
               }

        }
        if(j-1>=0&&bd[i][j-1]==false&&s[temp]==board[i][j-1])
        {

                temp = temp+1;
                bd[i][j-1] = true;
                if(find(s,len-1,i,j-1,m,n,board,bd))return true;
                else {
                    temp--;
                    bd[i][j - 1] = false;
                }
        }
        if(j+1<n&&bd[i][j+1]==false&&s[temp]==board[i][j+1])
        {

                temp = temp+1;
                bd[i][j+1] = true;
                if(find(s,len-1,i,j+1,m,n,board,bd))return true;
                else {
                    temp--;
                    bd[i][j + 1] = false;
                }
        }

        return false;
    }

    public static void main(String[] args) {
        char[][] board = {{'C','A','A'},
                {'A','A','A'},
                {'B','C','D'}};
        exist(board, "AAB");
    }
}